#include <iostream>
#include <string>
#include <stack>
using namespace std;

stack<char> a;

int main() {
	int n;
	cin >> n;
	while (n--) {
		string hex;
		cin >> hex;
		
		for (int i=0; i<hex.length(); i++) {
			char hex_digit;
			if (hex[i] >= 'A') hex_digit=hex[i]-'A'+10;
			else hex_digit=hex[i]-'0';
			a.push((hex_digit>>3)&1);
			a.push((hex_digit>>2)&1);
			a.push((hex_digit>>1)&1);
			a.push((hex_digit>>0)&1);
		}
		string oct = "";
		int size = a.size();
		for (int i=0; i<size; i+=3) {
			char d1, d2, d3;
			if (!a.empty()) { d3=a.top(); a.pop(); }
			else d3=0;
			if (!a.empty()) { d2=a.top(); a.pop(); }
			else d2=0;
			if (!a.empty()) { d1=a.top(); a.pop(); }
			else d1=0;
			char oct_digit = d1<<2|d2<<1|d3;
			oct += oct_digit+'0';
		}
		int start = oct.length()-1;
		if (oct[start] == '0') start--;
		for (int i=start; i>=0; i--) {
			cout << oct[i];
		}
		cout << endl;
	}
	return 0;
}
